package Leetcode第二期;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : K k
 * @date : 9:24 2020/10/3
 * 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
 *
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 */
public class 有效的数独_36 {

    //思路：三个hashmap或者三个双层数组
    public boolean isValidSudoku(char[][] board) {
        int size=board.length;
        boolean [][] row=new boolean[size][size];
        boolean [][] col=new boolean[size][size];
        boolean [][] box=new boolean[size][size];
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                if(board[i][j]!='.'){
                    int tem=board[i][j]-'1';          //取出当前位置的数并转化成 row、col和box的相应位置
                    int boxes=(i / 3 ) * 3 + j / 3;   //判断当前位置所在的包,是当前的位置，不是那个tem值所在的包
                    if(row[i][tem] || col[j][tem] || box[boxes][tem])
                        return false;
                    row[i][tem]=true;                 //标记row、col和box的相应位置已经访问过了
                    col[j][tem]=true;
                    box[boxes][tem]=true;

                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] board=new char[][]{
              {'5','3','.','.','7','.','.','.','.'},
              {'6','.','.','1','9','5','.','.','.'},
              {'.','9','8','.','.','.','.','6','.'},
              {'8','.','.','.','6','.','.','.','3'},
              {'4','.','.','8','.','3','.','.','1'},
              {'7','.','.','.','2','.','.','.','6'},
              {'.','6','.','.','.','.','2','8','.'},
              {'.','.','.','4','1','9','.','.','5'},
              {'.','.','.','.','8','.','.','7','9'}
        };
        有效的数独_36 x=new 有效的数独_36();
        System.out.println(x.isValidSudoku(board));
    }
}
